package com.learn;

import java.util.ArrayList;
import java.util.Scanner;

// Problem : Given a number N, build a symmentric matrix : t[A] = A
public class Matrix {

	/**
	 * @param args
	 * @throws Exception
	 */
	public static void main(String[] args) throws Exception {
		log("Enter even number : 4~18");
		Scanner scanner = new Scanner(System.in);
		int N = scanner.nextInt();
		if (N % 2 == 1 || N <= 2)
			throw new Exception("Invalid number. Require even number >2");
		char ar[][] = new char[N][N];

		for (int i = 0; i < ar.length; i++)
			// initialize
			for (int j = 0; j < ar.length; j++)
				ar[i][j] = '_';

		ArrayList<Character> elements = getElements(N);// populate
		for (int i = 0; i < N; i++) {
			ar[i][i] = elements.get(0);
			ar[i][N - i - 1] = elements.get(N - 1);
			ar[0][i] = ar[i][0] = elements.get(i);
		}
		// printAr("initial", ar);
		int[] nextPos = new int[2];
		getNextPosition(ar, 1, 1, nextPos);
		populate(ar, nextPos[0], nextPos[1]);
		printAr("FINAL", ar);
		log(checkTranspose(ar));

		// For testing getNextPosition()
		// while (nextPos[0] != -1) {
		// getNextPosition(ar, 0, 0, nextPos);
		// ar[nextPos[0]][nextPos[1]] = 'X';
		// printAr(" " + nextPos[0] + " " + nextPos[1] + ">>>>>>>", ar);
		// }

	}

	/**
	 * given partially populated array and (x,y) position, determines valid
	 * element for (x,y) by recursion and backtracking
	 */
	public static boolean populate(char[][] ar, int x, int y) {
		ArrayList<Character> elements = getElements(ar.length);
		// log("for " + x + " " + y);
		// removing existing chars
		for (int i = 0; i < ar.length; i++) {
			if (elements.contains(ar[i][y])) {
				// log("rem" + i + " " + y + " " + ar[i][y]);
				elements.remove(new Character(ar[i][y]));
			}

			if (elements.contains(ar[x][i])) {
				// log("removing2 " + x + " " + i + " " + ar[x][i]);
				elements.remove(new Character(ar[x][i]));
			}
		}

		do {
			if (elements.isEmpty())
				return false;
			// printAr("iter " + x + " " + y + "-> " + elements, ar);
			char substitutedElement = elements.remove(0);
			ar[x][y] = ar[y][x] = substitutedElement;
			if (x == ar.length - 2 && y == ar.length - 1) {
				return true;
			} else {
				int[] nextPos = new int[2];
				getNextPosition(ar, x, y, nextPos);
				if (populate(ar, nextPos[0], nextPos[1]))
					return true;
				else
					ar[x][y] = ar[y][x] = '_';
			}
		} while (elements.size() > 0);

		return false;// for now
	}

	/** for printing array */
	public static void printAr(String tag, char[][] ar) {
		log("Array: [ " + tag + " ]");
		for (int i = 0; i < ar.length; i++) {
			for (int j = 0; j < ar.length; j++)
				System.out.print(ar[i][j] + " ");
			log("");
		}
	}

	/** returns next unoccupied position in array (here, next 'X' co-ordinates) */
	public static void getNextPosition(char[][] ar, int x, int y, int outAr[]) {
		int nextX = x, nextY = y;
		while (nextX < ar.length && nextY < ar.length
				&& ar[nextX][nextY] != '_') {
			// log("not " + nextX + " " + nextY);
			nextY++;
			if (nextY >= ar.length) {
				nextY = 0;
				nextX++;
			}
		}
		if (nextX < ar.length && nextY < ar.length) {
			outAr[0] = nextX;
			outAr[1] = nextY;
		} else {
			outAr[0] = -1;
			outAr[1] = -1;
		}
	}

	/** utility function to return symbols for given n */
	public static ArrayList<Character> getElements(int n) {
		ArrayList<Character> list = new ArrayList<Character>();
		for (int i = 0, c = 'A'; i < n; i++)
			list.add((char) c++);
		return list;
	}

	/** for testing correctness of output */
	public static String checkTranspose(char ar[][]) {
		for (int i = 0; i < ar.length; i++)
			for (int j = 0; j < ar.length; j++)
				if (ar[i][j] != ar[j][i])
					return "fail";
		return "pass";
	}

	/** shorthand for System.out.println */
	public static void log(String s) {
		System.out.println(s);
	}
}
